package Year22_Month06.day17;

import java.util.LinkedList;
import java.util.Queue;

public class 另一棵树的子树_迭代写法 {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        Queue<TreeNode> queue = new LinkedList<>();//用来遍历第一个二叉树
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            //这里用迭代来写母树的遍历
            if(node != null){
                queue.offer(node.left);
                queue.offer(node.right);
                if(node.val == subRoot.val && isSame(node,subRoot)){
                    return true;
                }
            }
        }
        return false;
    }
    //这里用递归来写两颗二叉树的是否想同的遍历过程
    public boolean isSame(TreeNode node1,TreeNode node2){
        if(node1 == null && node2 == null) return true;
        if(node1 != null && node2 != null && node1.val == node2.val){
            return isSame(node1.left,node2.left) && isSame(node1.right,node2.right);
        }
        return false;
    }
}
